⟸ pàgina anterior ⟸

Exercici 8 (Tasca 4).

(decidable properties, context-free languages)

Propietats decidibles dels incontextuals

Sigui L_G un llenguatge (incontextual) generat per una gramàtica incontextual G. Donada la gramàtica G com a entrada, descriviu un algorisme que decideixi si

1. L_G és buit.
2. L_G és infinit.
3. L_G conté algun mot de mida parella.
4. L_G conté infinits mots de mida parella.

Quin és el cost asimptòtic de l’algorisme proposat com a funció del nombre de símbols de G?

Important

Més endavant en el curs veurem que per a tot un seguit de preguntes molt naturals sobre gramàtiques incontextuals no existeix cap algorisme que les decideixi. No és que encara no se n’hagi trobat un algorisme. No existeix cap algorisme que sempre acabi i retorni la resposta. Per exemple:

• Donada una gramàtica incontextual, és ambigua?
• Donada una gramàtica incontextual, descriu un llenguatge regular?
• Donada una gramàtica incontextual G amb terminals \{a,b\}, és L_G=\{a,b\}^*?
• Donades dues gramàtiques incontextuals G_1 i G_2, és L_{G_1}\cap L_{G_2} buit?
• Donades dues gramàtiques incontextuals G_1 i G_2, és L_{G_1}= L_{G_2}?
• Donades dues gramàtiques incontextuals G_1 i G_2, és L_{G_1}\subseteq L_{G_2}?